import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/1 11:21
 * @description 思路：用邻接表建图，然后给第一个人上红色，dfs这个人不喜欢的所有人为蓝色，继续dfs，直到存在冲突
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] dislikes = {{1, 2}, {1, 3}, {2, 3}};
        solution.possibleBipartition(4, dislikes);
    }

    /**
     * a b 之间存在的关系图
     */
    List<Integer>[] graph;
    Map<Integer, Integer> color;

    public boolean possibleBipartition(int N, int[][] dislikes) {
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; ++i) {
            graph[i] = new ArrayList();
        }

        for (int[] edge : dislikes) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        color = new HashMap();
        for (int node = 1; node <= N; ++node) {
            if (!color.containsKey(node) && !dfs(node, 0)) {
                return false;
            }
        }
        return true;
    }

    public boolean dfs(int node, int c) {
        if (color.containsKey(node)) {
            // 存在分配关系，返回分配的组和将要分配是否一致，发生冲突说明无法二分
            return color.get(node) == c;
        }
        // 不存在，那么分配
        color.put(node, c);
        // 分配讨厌的人到另一组，c^1，取反 初始值为0，那么要么0，要么1
        for (int nei : graph[node]) {
            if (!dfs(nei, c ^ 1)) {
                return false;
            }
        }
        return true;
    }
}
